package pers.vic.basics.leetcode;

import java.util.*;

/**
 * @author Vic.xu
 * @description: 82. 删除排序链表中的重复元素 II  {@literal https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/}
 * @date: 2021/1/20 0020 8:25
 */
public class J0082_M_DeleteDuplicates {

    /*
    给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     */

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Map<Integer, ListNode> map = new LinkedHashMap<>();
        Set<Integer> duplicatesKey = new HashSet<>();
        while (head != null) {

            int val = head.val;
            if (map.containsKey(val) || duplicatesKey.contains(val)) {
                map.remove(val);
                duplicatesKey.add(val);
            } else {
                map.put(val, head);
            }
            head = head.next;
        }

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (Map.Entry<Integer, ListNode> entry : map.entrySet()) {
            ListNode value = entry.getValue();
            if (value != null) {
                value.next = null;
            }
            cur.next = value;
            cur = value;

        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(new int[]{1,2,3,3,4,4,4,5});
        System.out.println(head);
        ListNode listNode = deleteDuplicates(head);
        System.out.println(listNode);
    }
}
